package codeTop;

import java.util.HashMap;
import java.util.Map;

public class q460 {
    static class LFUCache {
        class Node {
            int key;
            int value;
            int time;
            Node prev;
            Node next;
            public Node(int key,int value,int time) {
                this.key = key;
                this.value = value;
                this.time = time;
            }
            public Node(){}
        }

        Map<Integer,Node> queryMap;
        Map<Integer,Node> headMap;
        Map<Integer,Node> tailMap;
        int capacity;
        public LFUCache(int capacity) {
            queryMap = new HashMap<>();
            headMap = new HashMap<>();
            tailMap = new HashMap<>();
            this.capacity = capacity;
        }

        public int get(int key) {
            if (!queryMap.containsKey(key)) {
                return -1;
            }
            renew(key);
            return queryMap.get(key).value;
        }

        public void put(int key, int value) {
            if (queryMap.containsKey(key)) {
                queryMap.get(key).value = value;
                renew(key);
            }else {
                if (capacity == 0) {
                    //清出空间
                    for (int i = 1; i <=headMap.size() ; i++) {
                        if (headMap.get(i).next != tailMap.get(i)) {
                            Node node = tailMap.get(i).prev;
                            delete(node);
                            queryMap.remove(node.key);
                            capacity++;
                            break;
                        }
                    }
                }
                Node node = new Node(key, value, 0);
                addFirst(node);
                node.time++;
                queryMap.put(key,node);
                capacity--;
            }
        }

        public void renew(int key){
            Node node = queryMap.get(key);
            //先删除
            delete(node);
            //在添加到下一个链表中
            addFirst(node);
            node.time++;
        }

        public void delete(Node node){
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        public void addFirst(Node node){
            if (!headMap.containsKey(node.time + 1)) {
                Node head = new Node();
                Node tail = new Node();
                head.next = tail;
                tail.prev = head;
                headMap.put(node.time+1,head);
                tailMap.put(node.time+1,tail);
            }
            Node head = headMap.get(node.time + 1);
            node.prev = head;
            node.next = head.next;
            head.next = node;
            node.next.prev = node;
        }
    }

    public static void main(String[] args) {
        LFUCache cache = new LFUCache(2);
        cache.put(1,1);
        cache.put(2,2);
        System.out.println(cache.get(1));
        cache.put(3,3);
        System.out.println(cache.get(2));
        System.out.println(cache.get(3));
        cache.put(4,4);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }
}
